Digital halftoning converts continuous tone images from gray scale pixel values to a reduced number of pixel values. These smaller number of pixel values are utilized to convert the continuous tone images into images for use in a binary output device such as a binary printer, for example, through carefully arranging the position of printed dots produced by the binary printer. Halftoning may be applied to monochrome images or to a number of color planes of a color image.
Halftoning algorithms for producing patterns that are pleasing to the human eye can be categorized as either point or neighborhood algorithms according to the number of pixels from the input gray scale image required to calculate a single binary pixel output. In point algorithms, halftoning is accomplished by a comparison of the gray scaled image for a specific pixel against a halftone mask such as a Blue Noise mask or a Void and Cluster mask, for example, that is tiled across the image being scanned. For every point in the input image, a corresponding pixel of the output image is assigned a "1" or "0" depending on whether the value of the input pixel is larger than the value of the corresponding pixel in the halftone mask.
A gray scale, binary, printing process forms a black and white image by either placing a dot or not placing a dot of black ink at each printable pixel location. An input value of I=0 at a pixel location (x, y) represents the lightest printable color, white, which is produced by printing no dot at the location (x, y). An input value of I=255 at the pixel location (x, y) represents the darkest printable color, black, which is produced by printing a dot at the location (x, y).
Shades of gray other than white or black cannot be produced at the pixel location by this printing process since a dot is either printed or not printed at each location. Therefore, the shades of gray must be simulated by printing a pattern of dots over a wider area than just one pixel.
Accordingly, an input shade of gray having a value of I is produced over a selected area by printing a dot at each location of the selected area with a probability of I/255. On average, I dots out of every 255 locations are printed. If the selected area is too small, it may be impossible to place exactly on average I dots out of 255 locations over this area. Therefore, the shade of gray is not accurately reproduced but only approximated.
Table 1 represents an 8.times.8 square pixel mask.
TABLE 1 0 168 48 220 72 244 100 248 84 148 116 20 228 12 152 60 196 32 184 128 68 188 124 224 56 216 112 44 200 96 36 172 164 8 136 212 28 232 204 104 108 180 80 160 88 132 4 236 144 24 240 52 192 64 156 76 252 92 140 120 16 208 40 176
It should be noted that the threshold values in Table 1 are uniformly distributed with the threshold values spaced every four units from 0 to 252. The threshold values of Table 1 can be used to govern the probability of a dot being printed.
For example, if a gray level value of I=33 is to be produced over an entire 8.times.8 square pixel area with the threshold values given by Table 1, nine dots will be printed at the positions having threshold values of 0, 4, 8, 12, 16, 20, 24, 28, and 32. Therefore, the gray level value of I=33 is approximated by 9 dots out of 64 where 9/64 locations is approximately equal to 33/255. The nine dots are placed at the locations marked by X in Table 2. It is assumed that Table 2 was constructed so that this pattern of nine dots is a desirable arrangement of nine dots for a gray level value of I=33.
TABLE 2 X X X X X X X X X
Neighborhood algorithms such as error diffusion, for example, do not need a halftone mask. The halftoning technique of error diffusion is generally attributed to Robert Floyd and Louis Steinberg as set forth in "An Adaptive Algorithm for Spatial Gray Scale," 1975 SID International Symposium, Digest of Technical Papers, pp. 36-37. This algorithm is unlike a halftoning mask in that the decision to place or not to place a dot at the specific location (x, y) depends on the image values at other pixel locations.
If a black-and-white image having image values of I(x, y) is to be printed on a binary printer, assume that each pixel has associated with it a threshold value T which is invariant for x and y values. If I(x, y) equals only either 0 or 255, the image can be reproduced as intended since not printing a dot corresponds to printing a value of I=0 while printing a dot corresponds to printing a value of I=255.
The problem occurs when I(x, y) is not equal to 0 or 255 for some x and y location; this is usually the situation with items such as photographs, for example. In this situation, printing or not printing a dot causes there to be an error from the actual value of the input image. If a dot is placed at the position (x, y), an error equal to the amount of 255-I(x, y) is generated at the position (x, y). If a dot is not placed, an error equal to the amount I(x, y) is generated at the position (x, y).
The error diffusion algorithm calculates the error at the specific position as the result of quantization and diffuses this error to neighboring dots. If a dot is printed at the position (x, y), some amount of the error is subtracted from neighboring dots to decrease their probability of being printed to compensate for overprinting at the position (x, y). Similarly, if a dot is not printed at the position (x, y), some amount of the error is added to neighboring dots to increase their probability of being printed to compensate for underprinting at the position (x, y). The algorithm proposed by Floyd and Steinberg spreads 7/16 of the error generated at the position or location (x, y) to a location (x+1, y), 3/16 to a location (x-1, y+1), 5/16 to a location (x, y+1), and 1/16 to a location (x+1, y+1).
When the value I(x, y) is between 0 and 255, this value can be thought of as the number of dots out of 255 to printed. If I(x, y) is constant over a wide area, on average, I(x, y) dots out of 255 will be printed in this area.
Numerous enhancements have been suggested to enhance the output quality of error diffusion. These include varying the threshold value by some amount as a function of x and y, varying the order in which pixels are quantized, and varying the amount of error spread to neighboring pixels as well as the choice of pixels to which the error is spread.
The relatively simple Floyd and Steinberg technique requires, for each pixel, calculation of four separate error terms, weighted according to an error diffusion filter, with these four error terms being added to the four corresponding neighboring pixels. Thus, known error diffusion techniques are computationally intensive and time consuming.
With the pixel located at a specific location (x, y), the first error term of the Floyd and Steinberg technique is produced by 7/16 of the quantization error being distributed to the next pixel (x+1, y) to be scanned in the same line. The pixel at a location (x+1, y+1) in the next scan line and one unit to the right (if scanning from left to right) has 1/16 of the quantization error distributed thereto. The pixel disposed at a location (x, y+1) in the next scanned line below the processing pixel has 5/16 of the quantization error distributed thereto. The pixel at a location (x-1, y+1) in the next scanned line and one pixel prior to the processing pixel has 3/16 of the quantization error distributed thereto. The weight of the quantization error for each pixel is provided by the error diffusion filter.
Thus, the Floyd and Steinberg technique is computationally intensive. As a result, the Floyd and Steinberg technique is time consuming.
Furthermore, the Floyd and Steinberg technique produces halftone images with artifacts, which are apparent patterns known to the industry as "worms."
It has previously been suggested to reduce the artifacts through distributing the errors to more of the neighbors of the pixel being scanned but this further increases the computational time. One previously suggested technique is disclosed in U.S. Pat. No. 5,313,287 to Barton. The aforesaid Barton patent uses both a matrix and error diffusion with the error diffusion having a 3-weight filter to reduce the error diffusion processing time.
Another problem with the presently available error diffusion process is directional hysteresis. This is particularly apparent in areas having very light gray levels and very dark gray levels. It has previously been suggested to utilize a serpentine or boustrophedonic raster to break up the directionality of a normal raster. The aforesaid Barton patent utilizes more than one scan in the same direction before reversing the scanning direction.